package other;

class test{
    public static void main(String[] args) {
        int []arr = {4,5,8,2,3,9,7,1};
        radixSort(arr);

        for (int j : arr) {
            System.out.println(j);
        }

    }

    private static void radixSort(int[] arr) {
        //获得数组中最大的值
        int max = findMax(arr,0,arr.length-1);

        //需要遍历的次数，需要由最大数中的位数决定
        for(int i =1; max/i>0; i = i * 10){
            //初始化二维数组
            int[][] buckets = new int[arr.length][10];

            //获取每一位数字的
            for(int j = 0; j<arr.length;j++){
                int num = (arr[j] / i) % 10;

                //将其放入桶中
                buckets[j][num] = arr[j];
            }

            //回收桶里的元素
            int k =0;
            for(int j = 0;j<10 ;j++){

                for(int l = 0; l < arr.length ; l++){
                    if(buckets[l][j]!=0){
                        arr[k++] = buckets[l][j];
                    }
                }
            }
        }
    }


    public static int findMax(int[] arr,int L,int R){
        if(L==R){
            return arr[L];
        }else{
            int a = arr[L];
            int b = findMax(arr,L+1,R);

            return Math.max(a, b);
        }
    }

}




